package job.ali;

/**
 * @author wq
 *
 * 使用动态规划
 */
public class Piaoyangguohai {
    public static void main(String[] args) {
        Piaoyangguohai solution=new Piaoyangguohai();
        char[][] arrs={
                {'C','C','S','S'},
                {'S','S','S','S'},
                {'C','C','S','S'},
                {'S','S','C','C'}
                /*
                0 0 0 0
                0 0 0 0
                0 0 0 0
                0 0 0 0

                * */
        };
        int res=solution.helper(arrs);
        System.out.println(res);
    }


    /*
    动态规划
    只能计算从起点到终点，无法计算某一点返回来。
    同时状态方程需要在纸上打开，创建dp数组的时候需要灵活考虑相应情景
     dp[i][j]=Math.min(dp[i-1][j]+cost1,dp[i][j-1]+cost2);
    * */
    public int helper(char[][] arrs){
        int m=arrs.length;
        int n=arrs[0].length;
        int dp[][]=new int[m][n];

        dp[0][0]=0;
        for(int i=1;i<m;i++){
            dp[i][0]=dp[i-1][0]+getCost(arrs[i][0],arrs[i-1][0]);
        }

        for(int j=1;j<n;j++){
           dp[0][j]=dp[0][j-1]+getCost(arrs[0][j],arrs[0][j-1]);
        }


        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=Math.min(dp[i-1][j]+getCost(arrs[i-1][j],arrs[i][j]),dp[i][j-1]+getCost(arrs[i][j-1],arrs[i][j]));
            }
        }

        for (int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }


        return dp[m-1][n-1];
    }

    public int getCost(char ch1,char ch2){
        if(ch1=='C'&&ch2=='C'){
            return 3;
        }
        if(ch1=='S'&&ch2=='S'){
            return 2;
        }
        if((ch1=='C'&&ch2=='S')||(ch1=='S'&&ch2=='C')){
            return 5;
        }


        return 0;
    }

    /*
    广度优先搜索
    使用优先队列的广度优先搜索
    * */
}
